package com.leo.leetcode.s100;

import java.util.HashMap;
import java.util.Map;

/**
 *
 * @author xuexiaolei
 * @version 2017年11月20日
 */
public class T13RomantoInteger {
    /**
     * 用map效率会降低，空间因为包装类型也会变大
     * String.toArray并不友好，不如用s.charAt(),String本身就是一个char数组，都封装好了方法，自己何必再封装
     * @param s
     * @return
     */
    public static int romanToInt(String s) {
        if (s == null || "".equals(s)) return 0;
        Map<Character, Integer> map = new HashMap<>();
        map.put('I',1);
        map.put('V',5);
        map.put('X',10);
        map.put('L',50);
        map.put('C',100);
        map.put('D',500);
        map.put('M',1000);
        int res = 0;
        char[] cs = s.toCharArray();
        for (int i = 0; i < cs.length; i++) {
            char tmp = cs[i];
            if (i+1 < cs.length){
                char tmpNext = cs[i+1];
                //如果当前位比下一位小，则这个位是用来减的
                if (map.get(tmp) < map.get(tmpNext)){
                    res += map.get(tmpNext)-map.get(tmp);
                    i++;
                    continue;
                }
            }
            res += map.get(tmp);
        }
        return res;
    }

    /**
     * 特别取巧的方式
     * @param s
     * @return
     */
    public int romanToInt2(String s) {
        int result = 0;
        if(s.indexOf("IV") > -1) {
            result -= 2;
        };
        if (s.indexOf("IX") > -1) {
            result -= 2;
        };
        if (s.indexOf("XL") > -1) {
            result -= 20;
        };
        if (s.indexOf("XC") > -1) {
            result -= 20;
        };
        if (s.indexOf("CD") > -1) {
            result -= 200;
        };
        if (s.indexOf("CM") > -1) {
            result -= 200;
        };

        char[] Arr = s.toCharArray();

        for(int i = 0; i < Arr.length; i++) {
            if(Arr[i]=='M') result+=1000;
            if(Arr[i]=='D') result+=500;
            if(Arr[i]=='C') result+=100;
            if(Arr[i]=='L') result+=50;
            if(Arr[i]=='X') result+=10;
            if(Arr[i]=='V') result+=5;
            if(Arr[i]=='I') result+=1;
        }
        return result;
    }

    /**
     * 在数字范围内比map效率高很多，多用了一个int数组空间，优秀算法！！
     * @param s
     * @return
     */
    public int romanToInt3(String s) {
        int nums[]=new int[s.length()];
        for(int i=0;i<s.length();i++){
            switch (s.charAt(i)){
                case 'M':
                    nums[i]=1000;
                    break;
                case 'D':
                    nums[i]=500;
                    break;
                case 'C':
                    nums[i]=100;
                    break;
                case 'L':
                    nums[i]=50;
                    break;
                case 'X' :
                    nums[i]=10;
                    break;
                case 'V':
                    nums[i]=5;
                    break;
                case 'I':
                    nums[i]=1;
                    break;
            }
        }
        int sum=0;
        for(int i=0;i<nums.length-1;i++){
            if(nums[i]<nums[i+1])
                sum-=nums[i];
            else
                sum+=nums[i];
        }
        return sum+nums[nums.length-1];
    }

    public static void main(String[] args) {
        System.out.println(romanToInt("DCXXI"));//621
        System.out.println(romanToInt("DCCLIII"));//753
        System.out.println(romanToInt("CML"));//950
        System.out.println(romanToInt("CMXCV"));//995
        System.out.println(romanToInt("XIV"));//14
        System.out.println(romanToInt("MMXVI"));//2016
    }
}
